import collections


class Solution(object):
    def componentValue(self, nums, edges):
        total = sum(nums)
        value = max(nums)
        d_edges = collections.defaultdict(set)
        for u, v in edges:
            d_edges[u].add(v)
            d_edges[v].add(u)

        def dfs(node, target):
            ans = nums[node]
            for v in d_edges[node]:
                d_edges[v].remove(node)
                value = dfs(v, target)
                d_edges[v].add(node)
                if value == -1:
                    return -1
                else:
                    ans += value

            if ans == target:
                return 0
            else:
                if ans > target:
                    return -1
                else:
                    return ans

        for num in range(value, total + 1):
            if total % num == 0:
                target = num
                if dfs(0, target) == 0:
                    return total // num - 1

data = Solution()
nums = [6, 2, 2, 2, 6]
edges = [[0, 1], [1, 2], [1, 3], [3, 4]]
print(data.componentValue(nums, edges))
nums = [1, 2, 1, 1, 1]
edges = [[0, 1], [1, 3], [3, 4], [4, 2]]
print(data.componentValue(nums, edges))
